#ifndef _MYGRAPH_H
#include <stdio.h>

#define NUM 20//代表顶点的最大数目，用于邻接矩阵的定义 
#define MAX 10000//代表一个接近于无穷大的值 

 
typedef char vexType[3];//顶点的数据类型，可以接收 3 个字符，类型定义
//全局变量 
vexType vexs[NUM];/*顶点信息*/
int n,m;//n代表实际的从键盘输入的顶点数目，m代表边数 

/*创建无向网络的邻接矩阵*/
void creat_graph(int cost[NUM][NUM])
{    
    int i,j,k,w;
    printf("请输入顶点数和边数(中间用,隔开):");   
    scanf("%d,%d",&n,&m);
    
    printf("请输入顶点信息(如v0)，中间用空格隔开，顶点数为你刚才输入的顶点数:\n");  
    for (i=0;i<n;i++)     
        scanf("%s",vexs[i]);
    for (i=0;i<n;i++)       
      for (j=0;j<n;j++)
        cost[i][j]=0;
    printf("请输入两个顶点间的边和权值(i,j,w)，三个数之间用,隔开：\n");
    for (k=0;k<m;k++)      
    {
        scanf("%d,%d,%d",&i,&j,&w);
        cost[i][j]=w;
        cost[j][i]=w;//如果没有这条语句，无向网就变成了有向网 
    }    
    printf("创建成功!邻接矩阵为：\n");
     
    for (i=0;i<n;i++)       
    { 
        for (j=0;j<n;j++)
            printf("%-6d",cost[i][j]);
        printf("\n");
    }
}

//普利姆算法求最小生成树，cost为邻接矩阵的二维数组，start_v为出发结点的序号 
void prim(int cost[NUM][NUM],int start_v)
{
    //closest为邻接点数组，lowcost为权值数组 
    int closest[NUM],lowcost[NUM],i,j,k,min;
    
    //给两个数组初始化 
    for(i=0;i<n;i++)
    {
        lowcost[i]=cost[start_v][i];
        closest[i]=start_v;
    }
    
    printf("普利姆算法结果--（顶点,顶点,权值）\n"); 
    for(i=1;i<n;i++)//循环n-1次，每次求出最小生成树的一条边 
    {
        min=MAX;
        for(j=0;j<n;j++)
        {//查找值最小且不为0的顶点 
            if(lowcost[j]!=0&&lowcost[j]<min)
            {
                min=lowcost[j];
                k=j;
            }
        } 
        printf("%d,%d:%d\n",closest[k],k,lowcost[k]);
        lowcost[k]=0;
        for(j=0;j<n;j++)
        { 
            if(cost[k][j]!=0&&cost[k][j]<lowcost[j])
            {
                lowcost[j]=cost[k][j];
                closest[j]=k;
            }
        } 
    }
    
}


#endif 
